public class BitMap {
    private byte[] bits;
    private int size;

    public BitMap(long N){
        int initCap=getIndex(N)+1;
        bits=new byte[initCap];
    }

    public int getSize(){
        return size;
    }

    private int getIndex(long num){
        return (int)(num >> 3);
    }

    private int getLoc(long num){
        return (int)(num & 0x07);
    }

    private void expansion(long num){
        int tarSize=getIndex(num)+1;
        byte[] newBits=new byte[tarSize];
        for (int i = 0; i < bits.length; i++) {
            newBits[i]=bits[i];
        }
        bits=newBits;
    }

    public boolean contains(long num){
        int index=getIndex(num);
        if(index>=bits.length){
            return false;
        }
        return (bits[index] & 1 << getLoc(num)) != 0;
    }

    public void put(long num){
        int index=getIndex(num);
        if(index>=bits.length){
            expansion(num);
        }
        byte tmpSeg=bits[index];
        byte resSeg=(byte) (tmpSeg | 1 << getLoc(num));
        if(resSeg!=tmpSeg){
            bits[index]=resSeg;
            size++;
        }
    }

    public void remove(long num){
        int index=getIndex(num);
        if(index>=bits.length){
            return;
        }
        byte tmpSeg=bits[index];
        byte resSeg=(byte) (tmpSeg & ~(1 << getLoc(num)));
        if(resSeg!=tmpSeg){
            bits[index]=resSeg;
            size--;
        }
    }

    public long[] toNumArr(){
        long[] numArr=new long[size];
        int loc=0;
        long tmpNum=0;
        for (byte bit:bits) {
            for (int i = 0; i < 8; i++) {
                if(0!=(bit & 1 << i)){
                    numArr[loc]=tmpNum;
                    loc++;
                }
                tmpNum++;
            }
        }
        return numArr;
    }

    public static boolean dupCheck(BitMap bm1,BitMap bm2){
        byte[] bits1=bm1.bits, bits2=bm2.bits;
        int minLen=Math.min(bits1.length,bits2.length);
        for (int i = 0; i < minLen; i++) {
            if((bits1[i]&bits2[i])!=0){
                return true;
            }
        }
        return false;
    }
}
